package cn.edu.jxau.test;

import java.util.LinkedList;

public class Main {

    public static void main(String[] args) {

        Stack stack = new Stack();
        stack.push(3);
        System.out.println(stack.getMin());
        stack.push(4);
        stack.pop();
        System.out.println(stack.getMin());
        stack.push(5);
        System.out.println(stack.getMin());
        stack.push(1);
        stack.pop();
        System.out.println(stack.getMin());
        stack.push(2);
        System.out.println(stack.getMin());
        stack.push(1);
        System.out.println(stack.getMin());
    }
}

/**
 * 方案一
 * @author 付大石
 */
//class Stack {
//
//    private LinkedList<Integer> dataStack;
//    private LinkedList<Integer> minStack;
//
//    public Stack() {
//
//        dataStack = new LinkedList<>();
//        minStack = new LinkedList<>();
//    }
//
//    public void push(int item) {
//
//        dataStack.push(item);
//        if (minStack.isEmpty()) {
//            minStack.push(item);
//        } else {
//            if (item <= getMin()) {
//                minStack.push(item);
//            } else {
//                // nothing to do
//            }
//        }
//    }
//
//    public int pop() {
//
//        if (dataStack.isEmpty()) {
//            throw new RuntimeException("stack is empty");
//        }
//        int top = dataStack.pop();
//        if (top == getMin()) { //取出的是{@code dataStack}中的最小值
//            minStack.pop();
//        }
//        return top;
//    }
//
//    public int getMin() {
//
//        if (minStack.isEmpty()) {
//            throw new RuntimeException("stack is empty");
//        } else {
//            return minStack.peek();
//        }
//    }
//}


/**
 * 方案二
 * @author 付大石
 */
class Stack {

    private LinkedList<Integer> dataStack;
    private LinkedList<Integer> minStack;

    public Stack() {

        dataStack = new LinkedList<>();
        minStack = new LinkedList<>();
    }

    public void push(int item) {
        
        dataStack.push(item);
        if(minStack.isEmpty()) {
            minStack.push(item);
        } else {
            int curMin = getMin();
            if(item < curMin) {
                minStack.push(item);
            } else {
                minStack.push(curMin);
            }
        }
    }

    public int pop() {
        
        if(dataStack.isEmpty()) {
            throw new RuntimeException("stack is empty");
        }
        minStack.pop();
        return dataStack.pop();
    }

    public int getMin() {

        if (minStack.isEmpty()) {
            throw new RuntimeException("stack is empty");
        } else {
            return minStack.peek();
        }
    }
}